#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<iterator>
#include<fstream>
using namespace std;

#define STEPPRINT(content,pattern,pos)							\
						for(int i=0; i<content.size(); ++i)	\
							cout<<content[i]<<" ";		\
						cout<<endl;				\
						for(int i=0; i<pos+1-pattern.size(); ++i) \
							cout<<" "<<" ";			\
						for(int i=0; i<pattern.size(); ++i)	\
							cout<<pattern[i]<<" ";		\
						cout<<endl<<endl;		        \
						cin.get();
//用于vector的输出						
template<typename T>
ostream& operator << (ostream& out, const vector<T>& ivec);

//计算Delta1
void CalcDelta1(const string& pattern, vector<int>& delta1);
//计算rpr, The rightmost plausible reoccurrence
void CalcRpr(const string& pattern, vector<int>& rpr);
//根据rpr和patlen来计算出Delta2
void CalcDelta2(const string& pattern, const vector<int>& rpr, vector<int>& delta2);
//查找算法,根据delta1和delta2在content中查找pattern
void Search(const string& content, const string& pattern, const vector<int>& delta1, const vector<int>& delta2); 


int main()
{

	ifstream content_file("content.txt");
	ifstream pattern_file("pattern.txt");
	
	if(!content_file || !pattern_file)
	{
		cerr<<"Error: cann't open files"<<endl;
		exit(1);
	}

	string pattern("GCAG");
	string content("GCATCGCAGAGAGTATACAGTACGGCAGCAGAGAGTATACAGTACG");
	while(getline(pattern_file,pattern) && getline(content_file,content))
	{

		vector<int> delta1(26);

		vector<int> delta2(pattern.size());
		vector<int> rpr(pattern.size());

		CalcDelta1(pattern,delta1);
		cout<<delta1<<endl;

		CalcRpr(pattern,rpr);
		cout<<rpr<<endl;

		CalcDelta2(pattern,rpr,delta2);
		cout<<delta2<<endl;

		Search(content,pattern,delta1,delta2);
	}

}

//用于vector的输出						
template<typename T>
ostream& operator << (ostream& out, const vector<T>& ivec)
{
	ostream_iterator<T> output(out, " ");
	copy(ivec.begin(),ivec.end(),output);	
	return out;
}

//计算Delta1
void CalcDelta1(const string& pattern, vector<int>& delta1)
{
	int count=pattern.size()-1;
	//填充detal1的每一个元素的值为pattern.size()
	fill(delta1.begin(),delta1.end(),pattern.size());
	//注意，下面pattern[pattern.size()-1]位置并不会被处理
	for(int i=0; i<count; ++i)	
	{
		delta1[pattern[i]-'A']=count-i;
	}
}

//计算rpr, The rightmost plausible reoccurrence
void CalcRpr(const string& pattern, vector<int>& rpr)
{
	// 论文中的rpr的计算是通过扩展pattern来计算的，例如：
	// pattern:   
	// 	ABYXCDEYX（论文中的pattern例子）
	//
	// 扩展为：
	//	ABYXCDEYXABYXCDEYX
	//
	// 对应的下标为：
	// 	-8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9
	// 	 A  B  Y  X  C  D  E  Y  X  A  B  Y  X  C  D  E  Y  X
	//
	// 论文中关于rpr的定义是：
	// 	条件1：[pat(j+1) ... ... pat(patlen)]=[pat(k) ... ... pat(k+patlen-j-1)]
	// 	并且
	//      条件2：k<=1 or pat(k-1)!=pat(j)
	//
	// 那么上面给出的pattern中，我们来计算右边DEY这三个的rpr位置
	// 	-8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9
	// 	 A  B  Y  X  C  D  E  Y  X  A  B  Y  X  C  D  E  Y  X
	// Y的rpr:
	// 	1.首先Y所处的位置使j=8,[pat(j+1) ... ... pat(patlen)]="X"
	// 	2.确定k的位置，patlen-j-1实际上排除掉了pat(j+1)到pat(patlen)的内容，也就是说
	// 	  k+patlen-j-1的位置，实际上就是Y所处的位置。现在我们确定了要先从Y的位置向左
	// 	  开始扫描，最终找到符合条件1或者条件2的的位置k
	// 	3.扫描到k=4的时候，[pat(k) ... ... pat(k+patlen-j-1)]="X"，符合条件1，但是不符
	// 	  合条件2中的k<=1（此时k=4）或pat(k-1)（此时pat(k-1)=pat(3)="Y"）!=pat(j)，继
	// 	  续扫描。
	// 	4.扫描到k=0的时候，[pat(k) ... ... pat(k+patlen-j-1)]="X"，符合条件1，符合条件2
	// 	  中的k<=1。找到rpr=0
	// E的rpr:
	// 	1.j=7，要匹配的[pat(j+1) ... ... pat(patlen)]="YX".
	// 	2.从位置7开始向左进行扫描
	// 	3.扫描到k=3，符合条件1，符合条件2中的pat(k-1)!=pat(j)，找到rpr=3
	// D的rpr：
	// 	1.j=6，要匹配的[pat(j+1) ... ... pat(patlen)]="EYX"
	// 	2.从位置6开始向左扫描
	// 	3.扫描到k=-2，符合条件1，条件2中的k<=1
	
	//扩展pattern方便计算rpr
	string expand=pattern+pattern;
	//正在处理的rpr指针，因为pattern.size()-1位置的rpr始终是pattern的大小
	int rpr_index=pattern.size()-2;
	//最后一个rpr总是要移动pattern大小个位置，为什么？
	rpr[pattern.size()-1]=pattern.size();

	//由于size()返回的是unsigned int，会造成不必要的麻烦
	//在哪里用到了SIZE就是在哪里遇到了这个麻烦
	int SIZE=pattern.size();

	while(rpr_index>=0)
	{
		//由于进行了扩展，在expand中定位k的查找位置很麻烦，直接借pattern和rpr_index的值
		//得到在expand中开始从右往左扫描的位置
		int k_index=pattern.size()+rpr_index;
		//确定j的位置,只有符合条件1和条件2的j和k，才表明当前的k是正确的rpr
		int j_index=expand.size()-1;

		//用来定位k的下一次位置，具体作用在下面会明白
		int offset=0;

		while(1)
		{	
			// 在匹配[pat(j+1) ... ... pat(patlen)]=[pat(k) ... ... pat(k+patlen-j-1)]的时候
			// 要控制一共匹配多少个字符，rpr_index+pattern.size()刚好是pat(j)的位置，如果
			// rpr_index+pattern.size()=j_index则说明已经匹配到pat(j)的位置了，不符合前面所说
			// 的条件1
			if(expand[j_index]==expand[k_index] && rpr_index + pattern.size() < j_index)
			{
				--j_index;
				--k_index;


			// 到这一个判断的时候，可能已经匹配到了，也可能没有匹配到，这个判断来检查是不是
			// 因为rpr_index+pattern.size()<j_index条件不成立。
			//
			// 如果顺利匹配到j_index=pat(j)，则需要检查一下条件2
			}else if(rpr_index+pattern.size()==j_index && 				//顺利匹配到pat(j)
				(k_index-SIZE<2 || expand[k_index]!=expand[j_index]))	//检查条件2
			{
				//匹配成功
				break;


			// 执行到这里是因为第一个if中的expand[j_index]==expand[k_index]不成立
			// j_index要回到expand.size()-1准备下一次的匹配，k_index则要从
			// pat(j)-offset的位置开始
			}else
			{
				j_index=expand.size()-1;
				++offset;
				k_index=pattern.size()+rpr_index-offset;

			}
		}
		// 计算rpr
		// k_index+1是因为上面的--k_index，而在上面检查条件2的时候，k_index由于先进行递减使得
		// expand[k_index]刚好是pat(k-1)的位置，而j_index刚好是pat(j)的位置
		// 后面又有一个+1是因为这里的数组下标和论文中的不一样造成的，在上面说明rpr的定义的时候
		// 就可以看到，论文中的下标是从1开始的，C/C++是从0开始的。
		rpr[rpr_index]=k_index+1-pattern.size()+1;
		--rpr_index;
	}

}
//根据rpr和patlen来计算出Delta2
void CalcDelta2(const string& pattern, const vector<int>& rpr, vector<int>& delta2)
{
	for(int i=pattern.size()-1; i>=0; --i)
	{
		//直接套用论文中的公式
		delta2[i]=pattern.size()+1-rpr[i];
	}
}
//查找算法,根据delta1和delta2在content中查找pattern
void Search(const string& content, const string& pattern, const vector<int>& delta1, const vector<int>& delta2) 
{
	int content_index=pattern.size()-1;

	while(content_index<=content.size())
	{
		int pattern_index=pattern.size()-1;

		//打印每一步的过程
		STEPPRINT(content,pattern,content_index);
		
		//进行匹配
		while(content[content_index]==pattern[pattern_index] && pattern_index!=-1)
		{
			--content_index;
			--pattern_index;
		}

		//可能匹配成功了，也可能不成功，开始检查
		
		// 匹配失败
		if(pattern_index!=-1)
		{
			int delta1_move=delta1[content[content_index]-'A'];
			int delta2_move=delta2[pattern_index];
			//确定最大的移动步数
			int move=delta1_move>delta2_move?delta1_move:delta2_move;
			//移动
			content_index+=move;
		}else{
			cout<<"Found it at "<<content_index<<endl<<endl;
			//继续下一次的查找
			content_index+=pattern.size()+1;
		}
	}
}


